/*
https://leetcode.cn/problems/minimum-height-trees/description/
310. 最小高度树
方钊堉 2024.11.6
dfs
*/

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) { return {0}; }  // 如果只有一个节点，直接返回该节点

        vector<int> nodeDegrees(n); // 存储每个节点的度数
        vector<int> result; // 存储结果
        vector<vector<int>> adjacencyList(n); // 邻接表存储图结构

        // 构建邻接表和度数数组
        for (const auto& edge : edges) {
            int u = edge[0];
            int v = edge[1];
            ++nodeDegrees[u];
            ++nodeDegrees[v];
            adjacencyList[u].emplace_back(v);
            adjacencyList[v].emplace_back(u);
        }

        queue<int> leafNodes; // 存储当前层的所有叶子节点
        for (int i = 0; i < n; ++i) {
            if (nodeDegrees[i] == 1) {
                leafNodes.push(i); // 将所有初始叶子节点加入队列
            }
        }

        int remainingNodes = n; // 剩余节点数
        while (remainingNodes > 2) { // 当剩余节点数大于2时继续循环
            int layerSize = leafNodes.size(); // 当前层的叶子节点数
            remainingNodes -= layerSize; // 减少剩余节点数
            for (int i = 0; i < layerSize; ++i) {
                int currentNode = leafNodes.front();
                leafNodes.pop();
                for (auto neighbor : adjacencyList[currentNode]) {
                    if (--nodeDegrees[neighbor] == 1) {
                        leafNodes.push(neighbor); // 将新生成的叶子节点加入队列
                    }
                }
            }
        }

        // 最后剩下的1或2个节点即为最小高度树的根节点
        while (!leafNodes.empty()) {
            result.emplace_back(leafNodes.front());
            leafNodes.pop();
        }

        return result;
    }
};